/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-07 22:16:31
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-08 15:56:22
 * @FilePath: \LeetCode\215.数组中的第k个最大元素.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=215 lang=cpp
 *
 * [215] 数组中的第K个最大元素
 *
 * 方法1：快排的划分函数
 * - 每次快排确定一个数的最终位置
 * - 问题：时间开销巨大
 *
 * 官方题解：双路快速排序，让递归快速收敛
 * - 帮助程序在有大量重复数字时快速收敛边界
 * - 快速收敛就是让 `j` 尽可能接近当前区间中间位置
 * - 将 partition 与 getTopK 合并
 */

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstdlib> // 用于随机数生成
#include <ctime>   // 用于设置随机种子

// @lc code=start
class Solution
{
public:
    int m_k; // 第 k 个最大的元素 从小到大的位置
    int len;

    static int partition(std::vector<int> &nums, int low, int high)
    {
        /* 随机选择一个索引作为枢轴 */
        int randomIndex = low + rand() % (high - low + 1);
        /* 将随机选择的枢轴放到第一个位置 */
        std::swap(nums[randomIndex], nums[low]);

        int pivot = nums[low]; // 枢轴
        int i = low + 1;       // nums[low+1 ... i] < pivot
        int j = high;          // nums[j ... high]  > pivot
        while (true)
        {
            /* 双向逼近 */
            while (i <= high && nums[i] < pivot)
                i++;
            while (j >= low + 1 && nums[j] > pivot)
                j--;

            if (i > j)
                break;
            std::swap(nums[i], nums[j]);
            i++;
            j--;
        }
        std::swap(nums[low], nums[j]); // 不能只交换 pivot -> i=low+1
        return j;
    }

    int getTopK(std::vector<int> &nums, int low, int high)
    {
        int pivot_pos = partition(nums, low, high);
        if (pivot_pos == m_k)
            return nums[pivot_pos];
        else if (pivot_pos < m_k)
            return getTopK(nums, pivot_pos + 1, high);
        else
            return getTopK(nums, low, pivot_pos - 1);
    }

    int findKthLargest(std::vector<int> &nums, int k)
    {
        len = nums.size();
        m_k = len - k;                             // 从小到大的位置
        srand(static_cast<unsigned int>(time(0))); // 设置随机种子

        return getTopK(nums, 0, len - 1);
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {5, 2, 4, 1, 3, 6, 0};

    std::cout << solution.findKthLargest(nums, 4) << std::endl;

    return 0;
}